

#include <iostream>
#include <stack>//调用stack，利用栈来完成对二叉树的操作
using namespace std;
//二叉树的操作


typedef struct tree //二叉树节点的数据结构
{
    struct tree *left;//左指针
    int data;
    struct tree *right;//右指针
}tree, *Bitree;



void CreateTree(Bitree &T)//创建一个二叉树
{
    int data;
    scanf("%d", &data);
    if(data==-1)
    {
        T=NULL;//递归的终止条件
    } else{
        T=(Bitree)malloc(sizeof(tree));
        T->data=data;
        CreateTree(T->left);   //完成对函数的递归调用
        CreateTree(T->right);  //
    }
}

void  FirstVisit(Bitree &T)//递归先序便利
{
    if(T){
        printf("%d ", T->data);
        FirstVisit(T->left);
        FirstVisit(T->right);
    }
}


void  MiddleVisit(Bitree &T) {//递归中序便利
    if (T) {
        MiddleVisit(T->left);
        printf("%d ", T->data);
        MiddleVisit(T->right);
    }
}

void LastVisit(Bitree &T)//递归后序便利
{
    if(T) {
        LastVisit(T->left);
        LastVisit(T->right);
        printf("%d ", T->data);
    }
}

void menu()
{
    printf("关 于 二 叉 树 的 基 本 操 作\n");
    printf("1 先 序 创 建 二 叉 树\n");
    printf("2 递 归 遍 历 二 叉 树\n");
    printf("3 非 递 归 遍 历 二 叉 树\n");
    printf("0 退 出 程 序\n");
}

int main() {
    menu();
    int sc;
    Bitree T;
    while(true)
    {
        printf("请 输 入 你 的 选 择\n");
        scanf("%d", &sc);
        switch (sc)
        {
            case 0:
                exit(0);
            case 1:
                printf("输入你要创建的二叉树元素！！\n");
                CreateTree(T); printf("创建完成！！！\n");
                break;
            case 2:
                printf("先 序 递 归 输 出 如 下\n");
                FirstVisit(T);   printf("\n");
                printf("中 序 递 归 输 出 如 下\n");
                MiddleVisit(T);  printf("\n");
                printf("后 序 递 归 输 出 如 下\n");
                LastVisit(T);    printf("\n");
                break;

            default:break;
        }

    }

}